#include <stdio.h>
#include <string.h>
int main()
{
    int n,m,i,j,temp,t;
    scanf("%d",&t);
    while (t--){
    scanf("%d%d",&n,&m);
    int a[m+1][n+2],b[m+1][n+2];
    char str[m+1][n+2];
    for (i=0;i<m;i++)
      for (j=0;j<=n;j++)
        a[i][j]=0;
    for (i=0;i<m;i++)
    {
        scanf("%s",&str[i]);
        for (j=strlen(str[i])-1;j>=0;j--)
        {
            if (str[i][j]=='A')a[i][j]=a[i][j+1]+1;
            else if (str[i][j]=='C')a[i][j]=a[i][j+1]+100;
            else if (str[i][j]=='G')a[i][j]=a[i][j+1]+10000;
            else a[i][j]=a[i][j+1];
        }
        b[i][0]=0;
        for (j=0;j<strlen(str[i]);j++)
        {
            if (str[i][j]=='C')b[i][0]+=a[i][j]%100;
            else if(str[i][j]=='G')b[i][0]+=a[i][j]%100+(a[i][j]%10000)/100;
            else if(str[i][j]=='T')b[i][0]+=a[i][j]%100+(a[i][j]%10000)/100+a[i][j]/10000;
        }
        if (strlen(str[i])==1)b[i][0]=str[i][0];
        b[i][1]=i;
    }
    for (i=0;i<m;i++)
    {
        for (j=i+1;j<m;j++)
        {
            if (b[j][0]<b[i][0])
            {
                temp=b[i][0];b[i][0]=b[j][0];b[j][0]=temp;
                temp=b[i][1];b[i][1]=b[j][1];b[j][1]=temp;
            }
        }
    }
    for (i=0;i<m;i++)
    {
        for (j=0;j<n;j++)printf("%c",str[b[i][1]][j]);
        printf("\n");
    }}
    return 0;
}

